package leecode

func jewelleryValue(frame [][]int) int {
	dp := make([][]int, len(frame)) //dp数组为走到每一个位置上能拿到的珠宝最大价值
	for i := 0; i < len(frame); i++ {
		dp[i] = make([]int, len(frame[i]))
	}
	//初始化dp 每一次只能向右 或者 向下
	//从 0 , 0 走到 i , 0 只有一条路径
	dp[0][0] = frame[0][0]
	for i := 1; i < len(frame); i++ {
		dp[i][0] = frame[i][0] + dp[i-1][0]

	}
	//从0 , 0 走到 0 , j 的路径也只有一条
	for j := 1; j < len(frame[0]); j++ {
		dp[0][j] = frame[0][j] + dp[0][j-1]

	}
	for i := 1; i < len(frame); i++ {
		for j := 1; j < len(frame[i]); j++ {
			dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i][j]
		}
	}
	return dp[len(dp)-1][len(dp[0])-1]
}
